/*
 * @lc app=leetcode.cn id=57 lang=javascript
 *
 * [57] 插入区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  const result = [];
  // 判断newInterval是否放入结果
  let isInsert = false;
  let [left, right] = newInterval;

  for (const [l, r] of intervals) {
    // 位于newInterval右侧
    if (l > right) {
      // 首次将newInterval放入结果
      if (!isInsert) {
        result.push([left, right]);
        isInsert = true;
      }
      result.push([l, r]);
      // 位于newInterval左侧
    } else if (r < left) {
      result.push([l, r]);
    } else {
      // 与newInterval有交集，计算最大并集
      left = Math.min(left, l);
      right = Math.max(right, r);
    }
  }

  if (!isInsert) {
    result.push([left, right]);
  }

  return result;
};
// @lc code=end

/**
 * 时间复杂度：O(n)，其中 n 是数组 intervals 的长度
 * 空间复杂度：O(1)。除了存储返回答案的空间以外，我们只需要额外的常数空间
 */
